Graph Algorithms

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.

A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

{-# LANGUAGE FlexibleInstances #-}

module GraphTypes where

import Control.Monad.State
import qualified Data.Map as M
import qualified Data.Set as S

type NodeId = Int

data Graph = Graph {
    nodes :: S.Set NodeId,
    edges :: M.Map NodeId (S.Set NodeId)
} deriving (Show)

class Monad m => Grapher m where
    addNode :: NodeId -> m ()
    addEdge :: NodeId -> NodeId -> m ()

instance Grapher (State Graph) where
    addNode n = modify $ \g -> g { nodes = S.insert n (nodes g) }
    
    addEdge from to = modify $ \g -> 
        let currentEdges = M.findWithDefault S.empty from (edges g)
            newEdges = M.insert from (S.insert to currentEdges) (edges g)
        in g { edges = newEdges }

• Graph Partitioning Problems